#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <random>
#include <ctime>

const int gHashSize = 12;

template <typename T, typename U>
struct HashNode
{
    T _key;
    U _value;
};

template <typename T, typename U>
class HashTable
{
private:
    std::vector<std::list<HashNode<T, U>>> _vec;

public:
    HashTable(/* args */) : _vec(gHashSize)
    {
    }
    ~HashTable()
    {
    }

    int hash(const T &key)
    {
        return key % gHashSize;
    }

    bool insert(const T &key, const U &value)
    {
        HashNode<T, U> node;
        node._key = key;
        node._value = value;
        int index = hash(key);
        _vec[index].push_back(node);
        return false;
    }

    bool find(const T &key)
    {
        int index = hash(key);
        auto it = std::find_if(_vec[index].begin(), _vec[index].end(), [key](HashNode<T, U> n)
                               { return key == n._key; });
        if (it != _vec[index].end())
        {
            std::cout << it->_value << "\n";
            return true;
        }
        return false;
    }
};

// template <typename T, typename U>
// int hash(const T &key)
// {
//     return key % gHashSize;
// }

// template <typename T, typename U>
// bool HashTable::insert(const T &key, const U &value)
// {
//     HashNode<T, U> node;
//     node._key = key;
//     node._value = value;
//     for (int i = 0; i < gHashSize; i++)
//     {
//         if (i = hash(key))
//         {
//             _vec[i].push_back(node) return true;
//         }
//     }
//     return false;
// }
// template <typename T, typename U>
// bool HashTable::find(const T &key)
// {
//     int index = hash(key);
//     return std::find_if(_vec[index].begin(), _vec[index].end(), [key](HashNode<T, U> n)
//                         { return key == n._key; }) != _vec[index].end();
// }

int main(int argc, char const *argv[])
{
    HashTable<int, int> ht;
    long long int a = 1000;
    static std::default_random_engine e;
    static std::uniform_int_distribution<unsigned> u(0, 100);

    for (long long int i = 0; i < a; ++i)
        ht.insert(i, u(e));

    std::clock_t st = std::clock();
    ht.find(114);
    std::clock_t et = std::clock();
    std::cout << static_cast<double>(et - st) << "\n";
    return 0;
}
